import java.util.*;

/**
 * @author huangxunhui
 * Date: Created in 18/10/20 下午9:53
 * Utils: Intellij Idea
 * Description: 前K个高频元素
 */
public class TopKFrequent_347 {


    public List<Integer> topKFrequent(int[] nums, int k) {

        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int num : nums) {
            if(map.containsKey(num)){
                map.put(num , map.get(num) + 1);
            }else{
                map.put(num , 1);
            }
        }

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(
                (a , b ) -> map.get(a) - map.get(b)
        );

        for (Integer key : map.keySet()) {
            if(priorityQueue.size() < k){
                priorityQueue.add(key);
            }else if(map.get(key) > priorityQueue.peek()){
                priorityQueue.remove();
                priorityQueue.add(key);
            }
        }

        LinkedList<Integer> res = new LinkedList<>();
        while(!priorityQueue.isEmpty()){
            res.add(priorityQueue.remove());
        }
        return res;
    }
}
